package org.example.Soution001;

public class AncestorPro {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(37);
        root.left = new TreeNode(-34);
        root.right = new TreeNode(-48);
        root.left.right = new TreeNode(-100);
        root.right.left = new TreeNode(-101);
        root.right.right = new TreeNode(48);
        root.right.right.left = new TreeNode(-54);
        root.right.right.left.left = new TreeNode(-71);
        root.right.right.left.right = new TreeNode(-22);
        root.right.right.left.right.right = new TreeNode(8);
        AncestorPro ancestor = new AncestorPro();
        System.out.println(ancestor.lowestCommonAncestor(root,root.right.right.left.left,root.right.right).val);

    }

    TreeNode result=null;


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //后序遍历，对树进行剪枝，若某一枝上不存在p和q，则剪除
        //题目中已知p q必存在于树中
        cutBranch(root,p,q);
        return result;
    }

    public boolean cutBranch(TreeNode root, TreeNode p, TreeNode q) {
        //后序遍历
        if(root==null) return false;
        boolean left=cutBranch(root.left,p,q);
        boolean right=cutBranch(root.right,p,q);
        if((left&&right)||((root==p||root==q)&&(left||right))) {
            result = root;
        }
        return left||right||root==p||root==q;
    }
}
